package com.gali.leetcode.day9;

/**
 * @Auther: gali
 * @Date: 2022-07-22 19:42
 * @Description:
 */
public class Solution {
    /**
     * 链表
     */
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next;}
    }

    /**
     * 合并K个升序链表:递归(两两合并)
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null || lists.length==0) {
            return null;
        }
        return helper(lists,0,lists.length-1);
    }

    //通过mid将数组一分为二，并不断缩小规模，当规模为1时返回并开始合并
    //通过合并两个链表，不断增大其规模，整体看就是不断缩小-最后不断扩大的过程
    private ListNode helper(ListNode[] lists, int begin, int end) {
        if(begin==end) {
            return lists[begin];
        }
        int mid = begin+(end-begin)/2;
        ListNode left = helper(lists,begin,mid);
        ListNode right = helper(lists,mid+1,end);
        return merge(left,right);
    }

    //合并两个有序链表
    private ListNode merge(ListNode a, ListNode b) {
        if(a==null || b==null) {
            return (a==null) ? b : a;
        }
        if(a.val<=b.val) {
            a.next = merge(a.next,b);
            return a;
        } else {
            b.next = merge(a,b.next);
            return b;
        }
    }

    /**
     * 两两交换链表中的节点:递归
     * @param head 0-1-2-3-4-5
     * @return
     */
    public ListNode swapPairs(ListNode head) {
        if (head==null||head.next==null){
            return head;
        }
        ListNode res=head.next;
        head.next=swapPairs(res.next);
        res.next=head;
        return res;
    }
}
